Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring.
The same letter cell may not be used more than once.
For example, Given board =
[ ['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']]

• word = "ABCCED", -> returns true,
  
• word = "SEE", -> returns true,
  
• word = "ABCB", -> returns false.

题目大意：给定一个矩阵和一个字符串，判断矩阵中连续相邻的元素能否组成该字符串，同一个元素只能用一次。

题目难度：Medium

/**
 * Created by gzdaijie on 16/6/3
 * 深度优先搜索，若找到返回true，没有找到，就继续找
 */
public class Solution {
    private int[][] dirs = {{1, 0}, {-1, 0},{0, 1}, {0, -1}};

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        if (board[0].length == 0) return false;
        int m = board.length;
        int n = board[0].length;
        boolean[][] flag = new boolean[m][n];
        char ch = word.charAt(0);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == ch) {
                    flag[i][j] = true;
                    if (existRecursive(board, flag, word, 1, i, j)) return true;
                    flag[i][j] = false;
                }
            }
        }
        return false;
    }

    private boolean existRecursive(char[][] board, boolean[][] flag, String word, int index, int x, int y){
        if (index == word.length()) return true;

        int m = board.length;
        int n = board[0].length;
        char ch = word.charAt(index);
        boolean[] pos = new boolean[4];

        if (x < m - 1 && !flag[x + 1][y] && board[x + 1][y] == ch) pos[0] = true;
        if (x > 0 && !flag[x - 1][y] && board[x - 1][y] == ch) pos[1] = true;
        if (y < n - 1 && !flag[x][y + 1] && board[x][y + 1] == ch) pos[2] = true;
        if (y > 0 && !flag[x][y - 1] && board[x][y - 1] == ch) pos[3] = true;

        for (int i = 0; i < 4; i++) {
            if (!pos[i]) continue;
            int _x = x + dirs[i][0];
            int _y = y + dirs[i][1];
            flag[_x][_y] = true;
            if(existRecursive(board, flag, word, index + 1, _x, _y)) return true;
            flag[_x][_y] = false;
        }
        return false;
    }
}